package com.cwj.algorithm.graph;

import java.util.Deque;

/**
 * @author chenwujie
 * @date 2020-12-23 16:06
 * 拓扑排序
 */
public class TopoLogical {
    private Digraph digraph;
    private Deque<Integer> order;

    public boolean isCricoid() {
        return cricoid;
    }

    /**
     * 是否有环
     */
    private boolean cricoid;

    public TopoLogical(Digraph digraph){
        this.digraph = digraph;
    }

    /**
     * 拓扑排序
     * @return
     */
    public Deque<Integer> order(){
        if(hasCycle()){
            return null;
        }
        DepthFirstOrder depthFirstOrder = new DepthFirstOrder(digraph);
        Deque<Integer> order = depthFirstOrder.order();
        this.order = order;
        return order;
    }

    private boolean hasCycle(){
        DirectedCycle directedCycle = new DirectedCycle(digraph);
        directedCycle.checkCycle();
        boolean cricoid = directedCycle.isCricoid();
        this.cricoid = cricoid;
        return cricoid;
    }
}
